Advancement in technologies and an increase in electronic commercial transactions lead to frequent use of electronic signatures. As time goes by, use of electronic signatures, i.e., digital signatures, will be more accelerated. Use of an electronic signature must be accompanied with verification of the electronic signature. Meanwhile, some of servers or equipment need to make a verification of a large number of signatures at a time. For example, an electronic financial system of a bank is needed to efficiently verify a large number of certificates of authentication. Also, a vote protocol must be designed to fast verify a large amount of a voting result. Accordingly, an idea of batch verification has been introduced to expedite a signature verification.
Batch verification is an algorithm that verifies a plurality of signatures at a time. For batch verification, a method of verifying a large number of exponentiations at a time is mainly used. It is assumed that G is an abelian group having a generator g.
In batch verification, when a batch of n exponentiation pairs, e.g., {(x1, y1), (x2, y2), . . . , (xn, yn)}, are given, it is determined whether all values i satisfyyi=gxi at a time (i is an integer from 1 to n). Here, xi denotes an element of Z (a natural number field), and yi denotes an element of the abelian group G. That is, xiεZ and yiεG. In contrast, in general verification, not batch verification, whether each of the values i satisfyyi=gxi is individually verified.
FIG. 1 illustrates a plurality of signing devices 101, 102, . . . , 10n and a batch verification apparatus 120 for explaining conventional batch verification. Referring to FIG. 1, the signing devices 101, 102, . . . , 10n are connected to the batch verification apparatus 120 via a communication network 110. The batch verification apparatus 120 receives signature information that includes secret key information from each of the signing devices 101, 102, . . . , 10n. The batch verification apparatus 120 may store public key information therein or receive it together with a signature. The batch verification apparatus 120 extracts a batch {(x1, y1), (x2, y2), . . . , (xn, yn)}, for example, which are to be batch-verified based on the signature information and the public key information. Next, the batch verification apparatus 120 performs batch verification by checking whether all values i satisfyyi=gxi at the same time (i is an integer from 1 to n).
Accordingly, in batch verification, n exponentiation pairs are verified (batch-verified) in a batch by simultaneously checking whether they satisfy the equation given below, not by individually checking the n exponentiation pairs by checking whether (x1,y1) satisfiesy1=gx1, whether (x2,y2) satisfiesy2=gx2, and whether (xn,yn)satisfiesyn=gxn, for example.
                                          ∏                          i              -              1                        n                    ⁢                                          ⁢                      y            i                          =                  g                                    ∑                              i                =                1                            n                        ⁢                                                  ⁢                          x              i                                                          MathFigure        ⁢                                  ⁢        1            
An example of conventional batch verification is disclosed in U.S. Pat. No. 5,347,581 (hereinafter referred to as “'581 patent”. In '581 patent, when {(x1, y1), (x2, y2), . . . , (xn, yn)} are given, whether they satisfy the equation given below is determined for batch verification thereof.
                                          ∏                          i              =              1                        n                    ⁢                                          ⁢                      y            i                          r              i                                      =                  g                                    ∑                              i                =                1                            n                        ⁢                                                  ⁢                                          x                i                            ⁢                              r                i                                                                        MathFigure        ⁢                                  ⁢        2            
Equation (2) is obtained by raising the both sides of Equation (1) to power of ri,
where ri denotes l-bit integers randomly selected when a security parameter l is given. That is,riε{0,1}l where the integers ri are randomly selected from a set of l-bit numbers, each bit having a value of 0 or 1. That is, n ri(r1,r2, . . . , rn) are randomly selected from the set of numbers where a bit value is l and each bit is 0 or 1.
When the integers ri are selected from the set of l-bit integers being comprised of {0,1}, a probability that a verification error would occur is ½l. For example, the verification error indicates a case where at least one of the n pairs does not satisfyyi=gxi but Equation (2) is nevertheless satisfied thus allowing verification of all the n pairs to be passed.
According to '581 patent, the bit value l must be increased to reduce the probability that the verification error would occur. However, when the bit value l is increased, the computation amount of multiplication is increased to be proportional to the bit value l, thereby retarding the speed of verification.
Accordingly, it is highly desired to develop new high-speed batch verification with less amount of computation (particularly, computation amount of multiplication) than and with the same probability that the verification error would occur as batch verification disclosed in '581 patent, thereby improving the speed of verification.